package com.javaDemo.ti;

import java.util.*;

/**
 * 贪心算法经典问题详解
 * 
 * @author csy
 * @description 面试中常见的贪心算法题目的详细解析
 */
public class GreedyExamples {
    /**
     * 【区间问题】会议室安排
     * 
     * 问题描述：
     * 给定一个会议时间安排的数组intervals，其中intervals[i] = [start, end]，
     * 表示第i个会议的开始和结束时间。请你计算最多能安排多少个会议。
     * 
     * 解题思路详解：
     * 1. 为什么用贪心？
     * - 局部最优：优先安排结束时间早的会议
     * - 全局最优：能安排的会议数量最多
     * 
     * 2. 贪心策略证明：
     * - 假设最优解不包含结束最早的会议A
     * - 那么必然包含一个与A时间重叠的会议B
     * - 用A替换B，得到的方案不会比原方案差
     * - 因此，选择结束最早的会议一定是最优的
     * 
     * 3. 实现步骤：
     * a) 按结束时间排序
     * b) 选择第一个会议
     * c) 遍历剩余会议，如果开始时间晚于当前会议结束时间，则选择
     * 
     * 4. 举例详解：
     * 输入：[[1,4], [2,5], [3,6], [4,7], [5,8], [6,9]]
     * 排序后：[[1,4], [2,5], [3,6], [4,7], [5,8], [6,9]]
     * 选择过程：
     * - 选择[1,4]
     * - 可以选择[4,7]
     * - 可以选择[7,9]
     */
    public int maxMeetings(int[][] intervals) {
        if (intervals == null || intervals.length == 0)
            return 0;

        // 按结束时间排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int count = 1; // 第一个会议一定能安排
        int end = intervals[0][1]; // 当前安排的最后一个会议的结束时间

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= end) { // 当前会议的开始时间晚于上一个会议的结束时间
                count++;
                end = intervals[i][1];
            }
        }

        return count;
    }

    /**
     * 【分配问题】分发糖果
     * 
     * 问题描述：
     * n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。
     * 你需要按照以下要求，给这些孩子分发糖果：
     * 1. 每个孩子至少分配到1个糖果。
     * 2. 相邻两个孩子评分更高的孩子会获得更多的糖果。
     * 请你给每个孩子分发糖果，返回需要准备的最少糖果数目。
     * 
     * 解题思路详解：
     * 1. 为什么用贪心？
     * - 局部最优：保证每对相邻孩子评分高的获得更多糖果
     * - 全局最优：满足所有规则的情况下使用最少糖果
     * 
     * 2. 贪心策略：
     * - 两次遍历，分别处理左规则和右规则
     * - 左规则：当前孩子比左边孩子评分高时
     * - 右规则：当前孩子比右边孩子评分高时
     * 
     * 3. 实现步骤：
     * a) 初始化每个孩子一个糖果
     * b) 从左到右遍历，处理左规则
     * c) 从右到左遍历，处理右规则
     * 
     * 4. 举例详解：
     * 输入：ratings = [1,0,2]
     * 过程：
     * 初始：[1,1,1]
     * 左规则：[1,1,2]
     * 右规则：[2,1,2]
     */
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0)
            return 0;

        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1); // 每个孩子至少1个糖果

        // 从左到右遍历，确保右边评分高的孩子比左边的糖果多
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // 从右到左遍历，确保左边评分高的孩子比右边的糖果多
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        // 计算总和
        int sum = 0;
        for (int candy : candies) {
            sum += candy;
        }
        return sum;
    }

    /**
     * 【跳跃问题】跳跃游戏
     * 
     * 问题描述：
     * 给定一个非负整数数组nums，你最初位于数组的第一个下标。
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 判断你是否能够到达最后一个下标。
     * 
     * 解题思路详解：
     * 1. 为什么用贪心？
     * - 局部最优：每次都尽可能到达最远位置
     * - 全局最优：最终能够到达最后一个位置
     * 
     * 2. 贪心策略证明：
     * - 如果能到达某个位置，那么一定能到达它前面的所有位置
     * - 因此只需要关注能到达的最远位置
     * 
     * 3. 实现步骤：
     * a) 维护当前能到达的最远位置
     * b) 遍历数组，不断更新最远位置
     * c) 如果当前位置超过最远位置，则无法到达
     * 
     * 4. 举例详解：
     * 输入：nums = [2,3,1,1,4]
     * 过程：
     * - 位置0：最远能到达位置2
     * - 位置1：最远能到达位置4
     * - 位置2：最远能到达位置4
     * - 位置3：最远能到达位置4
     * - 位置4：已到达终点
     */
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0)
            return false;

        int maxReach = 0; // 当前能到达的最远位置

        for (int i = 0; i <= maxReach && i < nums.length; i++) {
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1)
                return true;
        }

        return false;
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        GreedyExamples solution = new GreedyExamples();

        // 测试会议室安排
        System.out.println("=== 会议室安排测试 ===");
        int[][] intervals = { { 1, 4 }, { 2, 5 }, { 3, 6 }, { 4, 7 }, { 5, 8 }, { 6, 9 } };
        System.out.println("会议时间安排：" + Arrays.deepToString(intervals));
        System.out.println("最多可以安排的会议数：" + solution.maxMeetings(intervals) + "\n");

        // 测试分发糖果
        System.out.println("=== 分发糖果测试 ===");
        int[] ratings = { 1, 0, 2 };
        System.out.println("孩子评分：" + Arrays.toString(ratings));
        System.out.println("最少需要的糖果数：" + solution.candy(ratings) + "\n");

        // 测试跳跃游戏
        System.out.println("=== 跳跃游戏测试 ===");
        int[] nums = { 2, 3, 1, 1, 4 };
        System.out.println("跳跃数组：" + Arrays.toString(nums));
        System.out.println("是否能到达最后一个位置：" + solution.canJump(nums));
    }
}